#include <stdio.h>
#include <stdlib.h>
// #define _POSIX_C_SOURCE 199309L   // 放在文件最顶端
#include <time.h>

/* 选择排序：升序，原地排序 */
/* 选择排序函数：把长度为 n 的 int 数组 a 按升序原地排序 */
void selection_sort(int a[], int n)
{
    /* 外层循环：i 指向当前“未排序区间”的第一个位置 */
    for (int i = 0; i < n - 1; ++i) {

        /* 假设当前 i 位置就是最小值的索引 */
        int min_idx = i;

        /* 内层循环：从 i+1 开始扫描剩余元素，找真正最小值的位置 */
        for (int j = i + 1; j < n; ++j) {
            /* 如果找到更小的元素，记录其下标 */
            if (a[j] < a[min_idx])
                min_idx = j;
        }

        /* 如果最小值不在 i 位置，则交换两者，把最小值放到正确位置 */
        if (min_idx != i) {
            int tmp      = a[i];  /* 用临时变量暂存 a[i] 的值 */
            a[i]         = a[min_idx];  /* 把最小值放到 a[i] */
            a[min_idx]   = tmp;         /* 把原来 a[i] 的值放到最小值原来的位置 */
        }
    }
}

/* 希尔排序（升序，原地）*/
void shell_sort(int a[], int n)
{
    /* 初始步长 gap = n/2，每次减半直到 0 */
    for (int gap = n / 2; gap > 0; gap /= 2) {

        /* 对每个“相隔 gap”的子序列做插入排序 */
        for (int i = gap; i < n; ++i) {
            int key = a[i];      /* 待插入元素 */
            int j = i;

            /* 向前跳跃 gap 步，找到 key 的合适位置 */
            while (j >= gap && a[j - gap] > key) {
                a[j] = a[j - gap];  /* 大元素后移 */
                j -= gap;
            }
            a[j] = key;  /* 插入到正确位置 */
        }
    }
}



/* ---------- 计时辅助 ---------- */
static double elapsed(const struct timespec *start,
                      const struct timespec *end)
{
    return (end->tv_sec - start->tv_sec) * 1e6 +
           (end->tv_nsec - start->tv_nsec) / 1e3;   /* 微秒 */
}

/* ---------- 主函数 ---------- */
int main(void)
{
    const int N = 1000;                 /* 测试规模，可自行调大/调小 */
    int *a = malloc(N * sizeof(int));
    if (!a) { puts("malloc failed"); return 1; }

    /* 生成同一组随机数据 */
    srand((unsigned)time(NULL));
    for (int i = 0; i < N; ++i) a[i] = rand();

    /* 备份数组，保证两种算法跑同一输入 */
    int *b = malloc(N * sizeof(int));
    if (!b) { puts("malloc failed"); return 1; }
    for (int i = 0; i < N; ++i) b[i] = a[i];

    struct timespec t0, t1;

    /* 1) 测试选择排序 */
    clock_gettime(CLOCK_MONOTONIC, &t0);
    selection_sort(a, N);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    printf("Selection sort: %.0f μs\n", elapsed(&t0, &t1));

    /* 2) 测试希尔排序（用备份数组，避免已排好序） */
    clock_gettime(CLOCK_MONOTONIC, &t0);
    shell_sort(b, N);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    printf("Shell      sort: %.0f μs\n", elapsed(&t0, &t1));

    free(a);
    free(b);
    return 0;
}
















// int main(void)
// {
//     int data[] = {42, 7, 13, 5, 99, 3};
//     int n = sizeof(data) / sizeof(data[0]);

// //     一行拆两句看：
// // sizeof(data)
// // 整个数组占的总字节数。
// // 例子里 int 通常 4 字节，6 个元素 ⇒ 4 × 6 = 24 字节。
// // sizeof(data[0])
// // 数组里单个元素占的字节数，即一个 int，一般 4 字节。
// // 于是：
// // int n = 24 / 4 = 6
// // 这样就得到了数组的元素个数，不需要手动写死 6。
// // 如果以后把数组改成 {1,2,3,4,5}，这段代码仍能自动算出 n = 5。
    

//     printf("Before: ");
//     for (int i = 0; i < n; ++i) printf("%d ", data[i]);
//     printf("\n");

//     selection_sort(data, n);

//     printf("After : ");
//     for (int i = 0; i < n; ++i) printf("%d ", data[i]);
//     printf("\n");

//     return 0;
// }